// 74. 搜索二维矩阵
// https://leetcode.cn/problems/search-a-2d-matrix/

/**
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
输出：false
 */

/**
 * 思路，用两次2分法
 * 第一次：找到对应的数组
 * 第二次：找到对应的数字，或找不到结果
 *
 */

/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
var searchMatrix = function (matrix, target) {
    const arr = findArray(matrix, target);

    if (arr === null) return false;

    const res = findNumber(arr, target);
};

var findArray = function (matrix, target) {
    // matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
    // [1,10,23]中，3>1,3<10,3<23

    let left = 0;
    let right = matrix.length - 1;
    let finalIndex = -1;

    while (left <= right) {
        const center = Math.floor((right + left) / 2);

        // if (center === left || center === right) {
        //     // 说明二分搜索已经到达终点
        //     finalIndex = center;
        //     break;
        // }

        const min = matrix[center][0];
        const max = matrix[center][matrix[center].length - 1];
        if (min <= target && max >= target) {
            left = center;
            right = center;
            finalIndex = right;
            break;
        } else if (min > target) {
            right = center - 1;
        } else {
            left = center + 1;
        }
    }

    console.log(
        `target ${target} in array ${JSON.stringify(matrix[finalIndex])}`
    );

    if (finalIndex === -1) {
        return null;
    }

    return matrix[finalIndex];
};

var findNumber = function (array, target) {
    let left = 0;
    let right = array.length - 1;
    let finalIndex = -1;
    while (left <= right) {
        const center = Math.floor((right + left) / 2);
        const headNumber = array[center];
        if (headNumber < target) {
            left = center + 1;
            finalIndex = left;
        } else if (headNumber > target) {
            right = center - 1;
            finalIndex = right;
        } else {
            left = center;
            right = center;
            finalIndex = right;
            break;
        }
    }

    let finalRes = !(left > right);
    console.log(
        `${target} is ${finalRes ? '' : 'not'} in ${JSON.stringify(array)}`
    );

    return finalRes;
};

// test

// findArray(
//     [
//         [1, 3, 5, 7],
//         [10, 11, 16, 20],
//         [23, 30, 34, 60],
//     ],
//     3
// );

// findArray(
//     [
//         [1, 3, 5, 7],
//         [10, 11, 16, 20],
//         [23, 30, 34, 60],
//     ],
//     13
// );

// searchMatrix(
//     [
//         [1, 3, 5, 7],
//         [10, 11, 16, 20],
//         [23, 30, 34, 60],
//     ],
//     3
// );

// searchMatrix(
//     [
//         [1, 3, 5, 7],
//         [10, 11, 16, 20],
//         [23, 30, 34, 60],
//     ],
//     13
// );

// searchMatrix([[1]], 1);

searchMatrix([[1], [3]], 3);
